package leetcode_acm.string;

import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月21日 19:59
 */
public class FindAnagrams {
    public List<Integer> findAnagrams(String ss, String tt) {
        List<Integer> list = new LinkedList<>();
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        /*滑动窗口预备*/
        int left = 0 , right = 0;
        int valid = 0;
        int[] windows = new int[26];
        /*需求窗口*/
        int[] need = new int[26];
        int needSize = 0;
        for (char c : t) {
            if(need[c] == 1){
                needSize++;
            }
            need[c]++;
        }
        /*开始滑动窗口寻找答案*/
        while(right < s.length){
            //向右滑动窗口
            int rightChar = s[right++];
            if(need[rightChar] != 0){
                windows[rightChar]++;
                if(need[rightChar] == windows[rightChar]){
                    valid++;
                }
            }
            while (right - left >= t.length){
                //当寻找到一个可行解的时候
                if(needSize == valid){
                    list.add(right);
                }
                int leftChar = s[left++];
                if(need[leftChar] != 0){
                    if(need[leftChar] == windows[leftChar]){
                        valid--;
                    }
                    windows[leftChar]--;
                }
            }
        }
        return list;
    }
}
